Leaf-similar trees¶
Time: O(N); Space: O(H); easy
Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
Example 1:
Input: {1,#,2,3}, {1,2,#,3}
Output: True
Explaination:
the first tree:
1
\
2
/
3
the second tree:
1
/
2
/
3
The leaf value sequence is: [3], so the same
Example 2:
Input: {1,#,2,3}, {1,2,#,3} Output: False
Explaination:
the first tree:
1
\
2
/
3
the second tree:
1
/ \
2 3
The first leaf value sequence is: [3], the second tree is: [2, 3], so it is not the same
Constraints:
Both of the given trees will have between 1 and 200 nodes.
Both of the given trees will have values between 0 and 200
1. Depth First Search¶
Intuition and Algorithm
Let’s find the leaf value sequence for both given trees. Afterwards, we can compare them to see if they are equal or not.
To find the leaf value sequence of a tree, we use a depth first search.
Our DFS function writes the node’s value if it is a leaf, and then recursively explores each child.
This is guaranteed to visit each leaf in left-to-right order, as left-children are fully explored before right-children.
[9]:
class TreeNode(object):
"""
Definition for a binary tree node.
"""
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution1(object):
"""
Time: O(T_1 + T_2). where T_1, T_2 are the lengths of the given trees.
Space: O(T_1 + T_2), the space used in storing the leaf values.
"""
def leafSimilar(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
def dfs(node):
if not node:
return
if not node.left and not node.right:
yield node.val
for i in dfs(node.left):
yield i
for i in dfs(node.right):
yield i
return all(a == b for a, b in zip(dfs(root1), dfs(root2)))
[10]:
s = Solution1()
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.right.left = TreeNode(3)
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.left.left = TreeNode(3)
assert s.leafSimilar(root1, root2) == True
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.right.left = TreeNode(3)
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)
assert s.leafSimilar(root1, root2) == False
[11]:
class Solution1a(object):
def leafSimilar(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
def dfs(node):
if node:
if not node.left and not node.right:
yield node.val
yield from dfs(node.left)
yield from dfs(node.right)
return list(dfs(root1)) == list(dfs(root2))
[12]:
s = Solution1a()
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.right.left = TreeNode(3)
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.left.left = TreeNode(3)
assert s.leafSimilar(root1, root2) == True
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.right.left = TreeNode(3)
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)
assert s.leafSimilar(root1, root2) == False